package com.ruben.leetCode;/**
 * @ClassName: PartitionLabelsSolution
 * @Date: 2020/10/22 0022 22:09
 * @Description:
 */

import java.util.*;

/**
 * @ClassName: PartitionLabelsSolution
 * @Description: 我还没有写描述
 * @Date: 2020/10/22 0022 22:09
 * *
 * @author: <achao1441470436@gmail.com>
 * @version: 1.0
 * @since: JDK 1.8
 */
public class PartitionLabelsSolution {

    public static void main(String[] args) {
        PartitionLabelsSolution solution = new PartitionLabelsSolution();
        List<Integer> list = solution.partitionLabels("ababcbacadefegdehijhklij");
        list.forEach(System.out::println);
    }

    public List<Integer> partitionLabels(String S) {
        List<Integer> result = new ArrayList<>(10);
        List<String> list = Arrays.asList(S.split(""));
        // 统计字母最后一次出现时的下标
        Map<String, Integer> lastIndexMap = new HashMap<>(1 << 4);
        for (int i = 0; i < list.size(); i++) {
            lastIndexMap.put(list.get(i), i);
        }
        // 每个区间的开始和结束下标
        int start = 0, end = 0;
        for (int i = 0; i < list.size(); i++) {
            // 获取当前片段当前字母出现过的最后一次下标
            end = Math.max(end, lastIndexMap.get(list.get(i)));
            // 如果达到前当前片段当前字母出现过的最后一次
            if (i == end) {
                // 计算区间长度，添加进结果
                result.add(end - start + 1);
                // 开始下个片段
                start = end + 1;
            }
        }
        // 返回结果
        return result;
    }
}
